#include <iostream>
#include <string>

using namespace std;

/* 
	Problem is, find the longest palindromatic substring of a string.

	Here is the link to the problem: http://www.leetcode.com/2011/11/longest-palindromic-substring-part-i.html
	This is the expanding approach that is solved using a O(N^2) time with O(1) space.
*/


// This function is to expand the string around center1 and center2
// from center1, go left-wards
// from center2, go right-wards
// until we could no longer find a matching char
// the reason why we have center1/2 is because the palindromatic could be "a" or "aa"
string ExpandAroundCenter(string s, int center1, int center2)
{
    int left = center1;
    int right = center2;
    int len = s.length();

	while (left >= 0 && right <= len-1 && s[left] == s[right])
	{
		left--;
		right++;
	}

    return s.substr(left+1, (right-1)-(left+1)+1);
}

string LongestPalindro(string s)
{
    if (s.length() == 0 || s.length() == 1)
        return s;

    int len = s.length();
    string longest = s.substr(0,1);
    
    // from each char, find the longest palindro for this point
    for (int i=0; i<len; i++)
    {
        string p1 = ExpandAroundCenter(s, i, i);
        if (p1.length() > longest.length())
            longest = p1;

        string p2 = ExpandAroundCenter(s, i, i+1);
        if (p2.length() > longest.length())
            longest = p2;
    }

    return longest;
}

int main()
{
    string s1 = "abba";
	string lps = LongestPalindro(s1);
    cout << "The longest palidromatic string for "+s1+" is: " + lps << endl;

    string s2 = "aaabbaaabbaaaa";
	lps = LongestPalindro(s2);
    cout << "The longest palidromatic string for "+s2+" is: " + lps << endl;

    cout<<"Press any key to terminate..."<<endl;

    return getchar();
}
